Texture mapping is an efficient and popular way to add details on surfaces in computer graphics applications. However, creating large and detailed texture maps is a difficult and tedious task. Moreover, these texture maps are usually at high resolution and often do not fit into available memory. Texture synthesis algorithms (such as sample-based texture synthesis techniques) are aimed at automatically generating large textures from a small example image (known as a texture sample or exemplar). Sample-based texture synthesis both reduces content creation time and storage requirements since the large texture can be generated from the exemplar and a set of parameters.
In general, sample-based texture synthesis takes an exemplar and generates additional content based on that exemplar to create much more content that is contained in the exemplar. Sample-based texture synthesis analyzes a given exemplar to create visually similar images. In graphics, these images often contain surface attributes like colors and normals, as well as displacement maps that define geometry itself. Sample-based texture synthesis alleviates the need to store explicitly an entire expanse of content. Instead, the content is generated “on the fly” from the much smaller exemplar.
Currently, there are several approaches to sampled-based texture synthesis. These approaches include tiling, patch optimization, and neighborhood-matching techniques. There are several types of tiling techniques. One of the simplest tiling techniques is to merely generate “tiled” content by creating multiple copies of the exemplar and placing them together in a tiled pattern. At large scales, the pattern of the exemplar appears repeatedly in the final content.
Another type of tiling technique precomputes a set of Wang Tiles designed to abut seamlessly along their boundaries. With a complete tile set, runtime evaluation is simple and parallel, and is therefore achievable in the graphics processing unit (GPU) pixel shader. In addition, this type of tiling technique allows some coarse control by transitioning between tiles of different textures.
Although tiling techniques are the fastest of the sampled-based texture synthesis techniques, their main drawback is that due to the fixed tile set the textures generated are repetitious and lack variety. In other words, the tiling techniques create generally unvaried and uninteresting results because of the large scale repetitions. Also, the regular tiling structure may become apparent when the texture is viewed from afar (or at large scale), especially for non-homogeneous textures.
Another type of sample-based texture synthesis is patch optimization. The patch optimization technique creates a texture by iteratively overlapping irregular patches of the exemplar to minimize overlap error. Dynamic programming or graph cut methods can be used to improve inter-patch boundaries. Because patch layout is a nontrivial optimization it is precomputed. Moreover, the layout process is inherently sequential. Control is possible by allowing a user override the delineation and positioning of patches. Although patch optimization techniques produce some of the best results of the sample-based texture synthesis techniques, their main drawback is that they lack much fine-scale adaptability during synthesis.
Yet another type of sample-based texture synthesis is neighborhood-matching. Neighborhood-matching techniques generate one pixel at a time in scanline or spiral order. For each pixel, the partial neighborhood already synthesized is compared with exemplar neighborhoods to identify the most likely pixels, and one pixel is chosen. The selected pixel is the pixel whose neighborhood best matches the currently synthesized neighborhood. Improvements to neighborhood-matching include hierarchical synthesis, fast vector-quantization (VQ) matching, coherent synthesis to favor patch formation, and precomputed similarity sets.
The major drawback with the neighborhood-matching, tiling, and patch optimization techniques is that they synthesize sequentially. For neighborhood-matching, sequential synthesis requires the use of a neighborhood that has already been synthesized to determine the current neighborhood. This introduces a “chain of dependencies” or “dependency chain” in the synthesis process. For tiling and patch optimization, sequential synthesis requires positioning of one tile or patch at time, such as in a left-to-right or a top-to-bottom fashion. For example, in order to find a location of a patch or tile in the middle of the texture, the entire texture up to that point must be generated. It is not possible to jump to one position and render a small window of texture. Instead, every single position between the beginning and the position must be generated. This is computationally expensive. Moreover, it is impractical to define huge deterministic landscapes because the entire image must be synthesized even if only a small portion of the landscape is visible or being displayed to a user.
At least one current neighborhood-matching technique attempts to achieve order-independent texture synthesis. The goal of this order-independent texture synthesis is to go to any arbitrary point in any arbitrary order and be able to synthesis texture. Instead of using a sequential search, the technique replaces each pixel by what is closest or best matches its neighbors. The technique uses a multi-resolution synthesis approach that is not implemented in parallel. In this multi-resolution or pyramid synthesis approach, multiple passes of pixel correction are applied at each pyramid level to match neighborhoods of the exemplar. The crucial innovation of this order-independent texture synthesis is to perform correction on all pixels independently, to allow deterministic synthesis of pixels in arbitrary order.
For example, the coarsest level (or level 0) is initialized with random colors. This is similar to sequential synthesis. Then, a sequence of correction passes are used that replace each pixel by the one pixel from the exemplar that best matches its current neighborhood. Each such correction pass is called a generation of synthesis. For the first generation at each level, a previous level is used to match colors at the coarser level to define the best matching coordinates for the next current level. Thus, in generation 0 of level 1, a 5×5 neighborhood of the coarser level 0 is used to infer the first coordinate for the next finer level (level 1). The 5×5 level 0 neighborhood is run over the exemplar, and a coherence search is used to speed up the search for a best matching neighborhood. For subsequent generations at each level, the neighborhood at both the current level and the previous coarser level are taken so that the search compares neighborhoods of both levels. For every pixel at a current level, a 5×5 neighborhood is used along with the previous coarser level.
By way of example, generation 0, level 1, is only generated using neighborhoods from level 0, generation 0. Generation 1 of level 1, uses neighborhoods from level 0, generation 0 and level 1, generation 0. Then, from level 1, generation 1, level 1, generation 2 is generated, using both neighborhoods from level 1, generation 1 and level 0, generation 0. Information from generation 2, level 1 is used to produce generation 0, level 2. When generation 1, level 2 is produced, neighbors from level 2, generation 0 and level 1, generation 2 are used (because it is the latest available). Thus, this order-independent texture synthesis technique considers only the best available generations of the current level and the previous level.
This order-independent texture synthesis technique “pulls” information forward instead of the majority of texture synthesis schemes, which “push” the information forward. In other words, requests for pixel are generated one at a time. Next, examination occurs of all the pixels at the different levels of generations that contribute to the final color.
One problem, however, with order-independent texture synthesis is that it is quite complex. Specifically, the approach uses a texture cache architecture (which is a per pixel demand-based architecture) that adds complexity. For each pixel, the cache contains information about which other pixels are required in the previous generations from the previous levels. If this information is not in the cache, then a cascade of evaluations must be computed. This means that if the graphics hardware wants to color a particular pixel, and if the pixel color is not in the texture cache, the graphics hardware must perform the above cascade of calculations to obtain this color.
Another problem with the order-independent texture synthesis scheme is that it is not implemented in parallel architecture, such as graphics processing units (GPUs). In fact, most neighborhood-matching synthesis algorithms cannot support parallel evaluation because their sequential assignment of output pixels involves long chains of causal dependencies. The computation cannot be mapped efficiently onto a parallel architecture like a GPU or multi-core central processing unit (CPU).
For the purpose of computer graphics, it is advantageous to implement texture synthesis on a parallel processor such as the GPU because the texture synthesis output is then written directly to video memory which is more easily accessible for graphics. If processing is performed on a CPU, the output must be transferred from system memory to the video memory. Implementation on a parallel processing unit such as the GPU discharges the CPU from texture synthesis and frees the CPU for other processing. Parallel processing on the GPU also allows real-time texture synthesis, and therefore alleviates the need to store vast amounts of texture and reduces memory consumption.
While many of the above-mentioned synthesis schemes offer some form of user guidance, they provide little control over the amount of texture variability. Typically, output variation is obtained by random seeding of boundary conditions (such as the random colors chosen to initialize the coarsest synthesis level). As one modifies the random seeds or adjusts algorithmic parameters, the synthesized result changes rather unpredictably. Thus, current sample-based texture synthesis techniques offer the user little control over the amount, placement and type of variation of the synthesized texture.